package mashibing.class21;

import java.util.HashMap;
import java.util.Map;

/**
 * arr是货币数组，其中的值都是正数。再给定一个正数aim。
 * 每个值都认为是一张货币，
 * 认为值相同的货币没有任何不同，
 * 返回组成aim的方法数
 * 例如：arr = {1,2,1,1,2,1,2}，aim = 4
 * 方法：1+1+1+1、1+1+2、2+2
 * 一共就3种方法，所以返回3
 */
public class Class21_4_CoinsWaySameValueSamePapper {

    public static class Info {
        public int[] coins;
        public int[] zhangs;

        public Info(int[] c, int[] z) {
            coins = c;
            zhangs = z;
        }
    }

    public static Info getInfo(int[] arr) {
        HashMap<Integer, Integer> counts = new HashMap<>();
        for (int value : arr) {
            if (!counts.containsKey(value)) {
                counts.put(value, 1);
            } else {
                counts.put(value, counts.get(value) + 1);
            }
        }
        int N = counts.size();
        int[] coins = new int[N];
        int[] zhangs = new int[N];
        int index = 0;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            coins[index] = entry.getKey();
            zhangs[index++] = entry.getValue();
        }
        return new Info(coins, zhangs);
    }

    public static int coinsWay1(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        Info info = getInfo(arr);
        return process(info.coins, info.zhangs, 0, aim);
    }

    // 1、暴力递归
    private static int process(int[] coins, int[] zhangs, int index, int rest) {
        if (index == coins.length) {
            return rest == 0 ? 1 : 0;
        }
        int way = 0;
        for (int zhang = 0; zhang <= zhangs[index] && zhang * coins[index] <= rest; zhang++) {
            way += process(coins, zhangs, index + 1, rest - zhang * coins[index]);
        }
        return way;
    }

    // 2、dp
    public static int coinsWay2(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        Info info = getInfo(arr);
        int[] coins = info.coins;
        int[] zhangs = info.zhangs;
        int[][] dp = new int[coins.length + 1][aim + 1];
        dp[coins.length][0] = 1;
        for (int index = coins.length - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                int way = 0;
                for (int zhang = 0; zhang <= zhangs[index] && zhang * coins[index] <= rest; zhang++) {
                    way += dp[index + 1][rest - zhang * coins[index]];
                }
                dp[index][rest] = way;
            }
        }
        return dp[0][aim];
    }

    // 3、dp优化
    public static int coinsWay3(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        Info info = getInfo(arr);
        int[] coins = info.coins;
        int[] zhangs = info.zhangs;
        int[][] dp = new int[coins.length + 1][aim + 1];
        dp[coins.length][0] = 1;
        for (int index = coins.length - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                int way = dp[index + 1][rest];
                if(rest - coins[index] >= 0) {
                    way += dp[index][rest - coins[index]];
                }
                if(rest - (zhangs[index] + 1) * coins[index] >= 0) {
                    way -= dp[index + 1][rest - (zhangs[index] + 1) * coins[index]];
                }
                dp[index][rest] = way;
            }
        }
        return dp[0][aim];
    }


    public static void main(String[] args) {
        int[] arr = {1, 2, 1, 1, 2, 1, 2};
        int aim = 4;
        System.out.println(coinsWay1(arr, aim));      // 3
        System.out.println(coinsWay2(arr, aim));      // 3
        System.out.println(coinsWay3(arr, aim));      // 3
    }
}
